#include <iostream>
#include <stack>
#include<queue>
#include<vector>
using namespace std;

template < typename Comparable >
class AvlTree
{
public:
    AvlTree()
    {}

    void insert(const Comparable& x)
    {
        insert(x, root);
    }

    void inorder() { inorder(root); }
    //成员参数队列s用于按序储存中序遍历后遍历到的AvlNode，便于后续对容器进行覆盖操作
    queue<Comparable> s;

    int count_settree = 0;

private:

   

    struct AvlNode
    {
        Comparable element;
        AvlNode* left;
        AvlNode* right;
        int height;

        AvlNode(const Comparable& ele, AvlNode* lt, AvlNode* rt, int h = 0)
            :element{ ele }, left{ lt }, right{ rt }, height{ h } { }

        AvlNode(Comparable&& ele, AvlNode* lt, AvlNode* rt, int h = 0)
            :element{ move(ele) }, left{ lt }, right{ rt }, height{ h } { }
    };

    AvlNode* root = nullptr;

    int height(AvlNode* t) const
    {
        return t == nullptr ? -1 : t->height;
    }


    void insert(const Comparable& x, AvlNode*& t)
    {
        if (t == nullptr)
        {
          t = new AvlNode{ x, nullptr, nullptr };
          count_settree++;
        }
            
        else if (x < t->element)
        {
          insert(x, t->left);
          count_settree++;
        }
            
        else if (t->element < x)
        {
           insert(x, t->right);
           count_settree++;
        }
            

        balance(t);
    }

    static const int ALLOWED_IMBALANCE = 1;

    void balance(AvlNode*& t)
    {
        if (t == nullptr)
            return;
        if (height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
            if (height(t->left->left) >= height(t->left->right))
                rotateWithLeftChild(t);
            else
                doubleWithLeftChild(t);
        else
            if (height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
                if (height(t->right->right) >= height(t->right->left))
                    rotateWithRightChild(t);
                else
                    doubleWithRightChild(t);
        t->height = max(height(t->left), height(t->right)) + 1;
    }

    void rotateWithLeftChild(AvlNode*& k2)
    {
        AvlNode* k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left), height(k2->right)) + 1;
        k1->height = max(height(k1->left), k2->height) + 1;
        k2 = k1;
    }

    void doubleWithLeftChild(AvlNode*& k3)
    {
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);
    }

    void rotateWithRightChild(AvlNode*& k2)
    {
        AvlNode* k1 = k2->right;
        k2->right = k1->left;
        k1->left = k2;
        k2->height = max(height(k2->right), height(k2->left)) + 1;
        k1->height = max(height(k1->right), k2->height) + 1;
        k2 = k1;
    }

    void doubleWithRightChild(AvlNode*& k3)
    {
        rotateWithLeftChild(k3->right);
        rotateWithRightChild(k3);
    }

    //通过递归实现中序遍历，按序将节点放入队列s
    void inorder(const AvlNode* t)
    {
        if (t == nullptr) return;
        inorder(t->left);
        s.push(t->element);
        inorder(t->right);

    }
}; 







template <class T>
class SplayTree
{
public:
    SplayTree() {}

    
    // 中序遍历"伸展树"
    void inOrder()
    {
        inOrder(mRoot);
    }

 
    // 旋转key对应的节点为根节点，并返回值为根节点。
    void splay(T key)
    {
        mRoot = splay(mRoot, key);
	}
    // 将结点(key为节点键值)插入到伸展树中
    void insert(T key)
    {
      SplayTreeNode* z = new SplayTreeNode(key,NULL,NULL);
        // 如果新建结点失败，则返回。
        /*if ((z = new SplayTreeNode(key, NULL, NULL)) == NULL)
	  return;*/
        // 插入节点
        insert(mRoot, z);
        // 将节点(key)旋转为根节点
        mRoot = splay(mRoot, key);
    }
    queue<T>  s;
    int count_settree = 0;
private:
    struct SplayTreeNode
    {
  
        T key;                // 关键字(键值)
        SplayTreeNode* left;    // 左孩子
        SplayTreeNode* right;    // 右孩子


        SplayTreeNode() :left(NULL), right(NULL) {}

        SplayTreeNode(T value, SplayTreeNode* l, SplayTreeNode* r) :
            key(value), left(l), right(r) {}
    };


    SplayTreeNode * mRoot=NULL;    // 根结点
    // 中序遍历"伸展树"
    void inOrder(SplayTreeNode* tree)
    {
        if (tree == NULL)
        {
            return;
        }
            inOrder(tree->left);
            T a = tree->key;
            s.push(a);
            inOrder(tree->right);
        

    }

   
    // 旋转key对应的节点为根节点，并返回值为根节点。
     SplayTreeNode* splay(SplayTreeNode* tree, T key)
    {
        SplayTreeNode N, *l, * r, * c;

        if (tree == NULL)
            return tree;

        N.left = N.right = NULL;
        l = r = &N;

        for (;;)
        {
            count_settree++;
            if (key < tree->key)
            {
                if (tree->left == NULL)
                    break;
                if (key < tree->left->key)
                {
		  c = tree->left;                           /* rotate right*/ 
                    tree->left = c->right;
                    c->right = tree;
                    tree = c;
                    if (tree->left == NULL)
                        break;
                }
                r->left = tree;                               /* link right */
                r = tree;
                tree = tree->left;
            }
            else if (key > tree->key)
            {
                if (tree->right == NULL)
                    break;
                if (key > tree->right->key)
                {
		  c = tree->right;                          /* rotate left */
                    tree->right = c->left;
                    c->left = tree;
                    tree = c;
                    if (tree->right == NULL)
                        break;
                }
                l->right = tree;                              /* link left */
                l = tree;
                tree = tree->right;
            }
            else
            {
                break;
            }
        }

        l->right = tree->left;                                /* assemble */
        r->left = tree->right;
        tree->left = N.right;
        tree->right = N.left;

        return tree;

     
    }
    // 将结点(z)插入到伸展树(tree)中
    void insert(SplayTreeNode*& tree, SplayTreeNode* z)
    {
        SplayTreeNode* y = NULL;
        SplayTreeNode* x = tree;

        // 查找z的插入位置
        while (x != NULL)
        {
            y = x;
            if (z->key < x->key)
            {
                x = x->left;
                count_settree++;
            }
            else if (z->key > x->key)
            {
                x = x->right;
                count_settree;
            }
                
          
        }
        if (y == NULL)
            tree = z;
        else if (z->key < y->key)
            y->left = z;
        else
            y->right = z;
    }
};

